package WangYI;

/**
 *
 */
import java.util.*;
public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int T = sc.nextInt();
            for (int i = 0; i < T; i++) {
                int n = sc.nextInt();
                int[] arr = new int[n];
                int total = 0;
                for (int j = 0; j < n; j++) {
                    arr[j] = sc.nextInt();
                    total += arr[j];  // 总价值
                }
                int min = Integer.MAX_VALUE;
                //System.out.println(Arrays.toString(arr));
                int[] dp = new int[n];
                dp[0] = arr[0];
                for (int j = 1; j < n; j++) {
                    for (int k = total/2; k >= arr[i]; k--) {
                        dp[k] = Math.max(dp[k],dp[k-arr[i]]+arr[i]);
                    }
                }

            }
        }
    }
}
